package practise.alogrithm.hundredInterviewQuestions;

import java.util.Arrays;
import java.util.HashSet;

/**
 * don't use extra place, remove the duplicated number in a array, the array is sorted.
 * Note, for place limited, nevertheless the number is sorted, we should use this method for sub cut this array.
 * if for a un-sorted array, the o complexity is nlogn.
 * if we can use a extra place for a unsorted array, then we just need a map for record the number times, and the o complexity is 2n
 */
public class RemoveDuplidateNumbers {
    public int[] removeDuplicate(int[] array){
        int endingPointer=0;
        HashSet<Integer> values = new HashSet<Integer>();
        for(int i=0;i< array.length;i++){
            int num = array[i];
            if(!values.contains (num)){
                array[endingPointer]= array[i];
                endingPointer ++;
            }
            values.add(num);
        }
        return Arrays.copyOf(array, endingPointer);
    }


    public static void main(String[] args){
        RemoveDuplidateNumbers removeDuplidateNumbers = new RemoveDuplidateNumbers();
        int[] result = removeDuplidateNumbers.removeDuplicate(new int[]{1,1,2,3,4,4,5,5,6,6});
        result.toString();
    }



}
